package leetcode.code0089;

import java.util.ArrayList;
import java.util.List;

public class Solution3 extends Solution89 {

	@Override
	public List<Integer> grayCode(int n) {
		int num = (int) Math.pow(2, n);// 总数量
		boolean[] used = new boolean[num];// 记录是否出现过
		List<Integer> ans = new ArrayList<>();// 答案
		grayCode(0, n, used, ans);// 从0开始, n位数字, 使用记录, 答案
		return ans;
	}

	private void grayCode(int num, int n, boolean[] used, List<Integer> ans) {
		used[num] = true;// 没出现过, 标记出现过了
		ans.add(num);// 记录答案
		for (int i = 0; i < n; i++) {
			int dif = 1 << i;// 所有位上, 尝试不同
			int next = num | dif;
			if (!used[next]) {
				this.grayCode(next, n, used, ans);
			}
		}
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
